package leecode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 *
 * @author qingyan 2021-07-02
 */
public class Question118 {

    public static void main(String[] args) {
        Question118 question = new Question118();
        System.out.println(question.generate(5));
    }


    public List<List<Integer>> generate(int numRows) {
        return dp(numRows);
    }

    /*
        方案一、动态规划
        dp[i][0] = dp[i-1][0]
        dp[i][1] = dp[i-1][0]+dp[i-1][1]
        ...
    */
    List<List<Integer>> dp(int numRows) {
        List<List<Integer>> dp = new ArrayList<>();
        if (numRows == 0) {
            return dp;
        }
        List<Integer> dp1 = new ArrayList<>();
        dp1.add(1);
        dp.add(dp1);
        if (numRows == 1) {
            return dp;
        }
        for (int i = 1; i < numRows; i++) {
            List<Integer> dpi = dp.get(i - 1);
            List<Integer> dpi2 = new ArrayList<>(dpi.size() + 1);
            dpi2.add(1);
            for (int i1 = 1; i1 < dpi.size(); i1++) {
                dpi2.add(dpi.get(i1 - 1) + dpi.get(i1));
            }
            dpi2.add(1);
            dp.add(dpi2);
        }
        return dp;
    }

}
